package com.itheima.leetcode.od.c.backtracking;

import java.util.*;

/**
 * <h3>数字排列</h3>
 */
public class NumberArrangement {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] nums = Arrays.stream(sc.nextLine().split(","))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(solution(nums));
    }

    public static int solution(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        int n = Integer.MIN_VALUE;

        for (int num : nums) {
            if (num < 1 || num > 9) {
                //  输入的数字不在范围内
                return -1;
            } else {
                set.add(num);
                n = Math.max(n, num);
            }
        }

        // 输入的数字有重复
        if (set.size() != 4) {
            return -1;
        }

        // 屏幕不能同时给出 2 和 5
        if (set.contains(2) && set.contains(5)) {
            return -1;
        }

        // 屏幕不能同时给出 6 和 9
        if (set.contains(6) && set.contains(9)) {
            return -1;
        }

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(2, 5);
        map.put(5, 2);
        map.put(6, 9);
        map.put(9, 6);

        boolean[] vis = new boolean[nums.length];

        String path = "";

        // 记录排列
        ArrayList<Integer> res = new ArrayList<>();

        // 排列求解
        dfs(nums, vis, path, map, res);

        // 给出这几个数字可拼成的数字从小到大排列位于第 N 位置的数字
        res.sort((a, b) -> a - b);

        // N为给出数字中最大的，如果不到这么多数字则给出最后一个即可
        n = Math.min(n, res.size());
        return res.get(n - 1);
    }

    // 排列求解
    public static void dfs(int[] nums, boolean[] visit, String path, HashMap<Integer, Integer> map, ArrayList<Integer> res) {
        if (!path.isEmpty()) {
            res.add(Integer.parseInt(path));
        }

        if (path.length() == nums.length) {
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visit[i]) {
                continue;
            }

            visit[i] = true;

            dfs(nums, visit, path + nums[i], map, res);

            // 2 可以当作 5 来使用，5 也可以当作 2 来使用进行数字拼接
            // 6 可以当作 9 来使用，9 也可以当作 6 来使用进行数字拼接
            if (map.containsKey(nums[i])) {
                dfs(nums, visit, path + map.get(nums[i]), map, res);
            }

            visit[i] = false;
        }
    }
}